Abstract Radix-Tree is a space optimized data structure that performs data compression by means of cluster nodes that share the same branch. Each node with only one child is merged withits child and is considered as space optimized. Nevertheless, it can€t be considered as speed optimized because the root is associated with theempty string. Moreover, values are not normally associated with every node; they are associated only with leaves and some inner nodes that correspond to keys of interest. Therefore, it takes time in moving bit by bit to reach the desired word. In this paper we proposethe KP-Trie which is consider as speed and space optimized data structure that is resulted from both horizontal and vertical compression.

References

[1]Askitis N. and SinhaR., HAT-trie:A Cache- Conscious Trie-basedData StructureforStrings, inProceedings of the30thAustralasian Conferenceon Computer science,pp. 97-105, 2007.

[2]Askitis N. and ZobelJ., Redesigning the String Hash Table, BurstTrie, and BST to Exploit Cache, Journal of Experimental Algorithmics, vol . 15,no. 1, 2011.

[3]Bando M. and ChaoJ., FlashTrie: Hash-based Prefix-Compressed Trie for IP Route Lookup Beyond 100Gbps, in Proceedings ofIEEE Communications SocietySubject Matter Experts for publication in the IEEE INFOCOM,San Diego,pp. 1-9, 2010.

[4]Behdadfar M. and SaidiH., The CPBT:A MethodforSearchingthePrefixesusingCoded Prefixesin B-tree, inProceedings of the 7th InternationalIFIP-TC6Networking Conference on AdHoc andSensor Networks,Wireless Networks, Next GenerationInternet,Singapore, pp.562-573, 2008.

[5]BodonF.and RonyalL.,Trie: An Alternative Data Structure for Data Mining Algorithms, Mathematical and Computer Modelling,vol. 38, no. 7-9, pp.739-751, 2003.

[6]FerraginaP. and GrossiR.,theString B-Tree: A NewDataStructureforString Search in External Memory and itsApplications, Journal of the ACM,vol. 46, no.2, pp. 236-280, 1999.

[7]FredkinE., Trie Memory, Communications of the ACM,vol. 3,no. 9, pp. 490-499, 1960.

[8]FuJ., HagsandO., and KarlssonG., Improving andAnalyzingLC-TriePerformance for IP- Address Lookup, JournalofNetworks,vol. 2, no. 3,pp. 1-10,2007.

[9]HanandehF., AlsmadiI., and KwafhaM., Evaluating Alternative Structures for Prefix Trees, inProceedings of World Congress on Engineering and Computer Science,San Francisco, pp.109-114, 2014.

[10]HeinzS.,ZobelJ., and WilliamsH.,BurstTries: aFast,Efficient Data StructureforString Keys, available at:http://goanna.cs.rmit.edu.au/ ~jz/fulltext/acmtois02.pdf,last visited2002.

[11]KnuthD.,TheArtofComputer Programming Sortiand Searching,RedwoodCity, USA, 1998.

[12]LeisV., KemperA., and NeumannT., The Adaptive Radix Tree:ARTful Indexing for Main- Memory Databases, available at: http://db.in.tum.de/~leis/papers/ART.pdf,last visited2013.

[13]Mih escu M.and BurdescuD.,Using M Tree Data Structure asUnsupervised Classification Method, Informatics,vol. 36,pp. 153-160, 2012.

[14]MorrisonD.,PATRICIA-Practical Algorithm ToRetrieveInformationCoded in Alphanumeric, Journal of the ACM,vol. 15,no. 4,pp.514-534, 1968.

[15]Mount D. and ParkE.,A Dynamic Data Structurefor Approximat Range Searching, in Proceedings of the26thAnnual Symposiumon Computational Geometry,Snowbird,pp.247- 256, 2010.

[16]NilssonS.andTikkanenM., An Experimental Study of Compression Methods for Dynamic Tries, Algorithmica,vol. 33,no. 1,pp.19-33, 2002.

[17]ParkG.,HwangH.,Nicod`emeP., and SzpankowskiW.,Profiles of Tries, Society for Industrial and Applied Mathematics,vol. 38,no. 5, pp. 1821-1880, 2009.

[18]Patel P. and GargD.,Comparison of Advance TreeDataStructures, InternationalJournalof ComputerApplications,vol. 41,no. 2,pp. 11-21, 2012.

[19]ReznikY.,SomeResultsonTrieswith Adaptive Branching, TheoreticalComputer Science,vol. 289,no. 2,pp.1009-1026, 2002.

[20]Sha eiN.,Non-blocking Patricia Tries with Replace Operations, inProceedings of the33rd International Conference on Distributed Computing Systems,Toronto,pp. 216-225, 2013.

[21]Yan K., Zhu H., LuK.,VParC: A Compression Scheme for Numeric Data in Column-oriented KP-TrieAlgorithmfor Update and Search Operations728 Databases, TheInternational Arab Journal of Information Technology,vol. 13, no. 1, published online,2016. Feras Al-Hanandehis currently an Associate Professor at the Prince Al Hussein Bin Abdullah II, Faculty of Information Technology, Al- Hashemite University, Jordan. He obtained his PhDdegreein Computer Science from the University Putra Malaysia, Malaysia, in 2006. His current research interests include distributed databases, parallel databases focusing on issues relatedto integrity maintenance, transaction processing and query processing. Izzat Alsmadiis a PhD in Software Engineering from NDSU, 2008. Currently; he is an Associate Professor in CIS Department at Boise State University, USA. MohammedAkourisan Assistant Professor in theDepartment of Computer Information Systemat Yarmouk University. He got his Bachelor (2006) and Master (2008)degree from Yarmouk University in Computer Information System withHonor.He joinedYU againinApril 2012 after graduatingwith his PhD inSoftware Engineeringfrom NDSU withHonor. EssamAl Daoudreceived hisBSc degreefrom Mu tah University, MSc degreefrom Al al-bayt University and his PhDdegreeinComputer Sciencefrom University Putra Malaysia in 2002.Currently, heisan associate professor and the chairman ofComputer Science Departmentat Zarka University. His research interests includemachine learning, soft- computing, cryptography, bioinformatics, quantum cryptography, quantum computation,DNAcomputing, nano-technology.